package _4_重建二叉树;

/**
 * 题目描述：
 * <p>
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列
 * {1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
 */

/**
 * 思路
 * 递归调用，先找到前序遍历的头，就是根，然后在中序遍历中找到它，前半部分是左子树，有半部分是右子树，
 * 递归即可
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        return digui(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }

    public TreeNode digui(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
        //if(preStart<=preEnd &&preEnd<pre.length){
        int rootVal = pre[preStart];
        TreeNode root = new TreeNode(rootVal);
        int index = inStart;
        while (index <= inEnd && rootVal != in[index]) {
            index++;
        }
        int leftLen = index - inStart;
        int rightLen = inEnd - index;

        if (leftLen != 0) {
            root.left = digui(pre, preStart + 1, preStart + leftLen, in, inStart, index - 1);
        }
        if (rightLen != 0) {
            root.right = digui(pre, preStart + 1 + leftLen, preEnd, in, index + 1, inEnd);
        }
        return root;
//        }
//        else{return null;}
    }

    public TreeNode digui2(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
        int rootVal = pre[preStart];
        TreeNode root = new TreeNode(rootVal);
        int index = inStart;
        while (index <= inEnd && rootVal != in[index]) {
            index++;
        }
        int leftLen = index - inStart;
        int rightLen = inEnd - index;
        if (leftLen != 0) {
            root.left = digui2(pre, preStart + 1, preStart + leftLen, in, inStart, index - 1);

        }
        if (rightLen != 0) {
            root.right = digui2(pre, preStart + leftLen + 1, preEnd, in, index + 1, inEnd);
        }
        return root;
    }
}